When contemplating the problem of optimizing a schedule (i.e. of identifying a schedule that is considered as satisfactory and/or as more satisfactory than a starting schedule), several complex and interacting aspects have to be considered. A schedule can generally be defined as a set of associations between tasks or jobs and workers, persons, groups of persons/workers or anyone/anything able to carry a task. There can be hard constraints associated with the situation, for example, a worker may not have more than n tasks associated to it, a worker can only be associated a task if they have the minimum required skills for carrying out the task, etc. Such hard constraints define what a feasible schedule is and what an unfeasible schedule is amongst the universe of possible (feasible and infeasible) schedules: a schedule that violates at least one hard constraint will be considered an infeasible schedule while all other schedules will be considered feasible schedules. As the skilled person knows, for a schedule to be a suitable schedule, the schedule must be a feasible schedule such that the search for a suitable schedule should search a suitable schedule amongst the feasible schedules and should not select an infeasible schedule. At the same time, the suitable schedule should attempt to optimize some aspects as much as possible. Examples of aspects that the schedule may attempt to optimize may include for example any of: a number of soft constraints violated (to be reduced), a number of consecutive tasks allocated during a worker's shift (to be increased so as to reduce the number empty slots), an amount of overtime (to be reduced), a travel distance (to be reduced), etc. These aspects to optimize can be taken into account in one or more cost functions which should be minimised (or maximised) for the best schedules. The problem of finding a suitable schedule for a set of tasks and workers can therefore involve trying to identify a suitable feasible solution among the vast number of possible solutions for allocating the tasks to the workers, while trying optimize one or costs functions.
Another point which affects the complexity of identifying a suitable schedule is that neighboring or similar schedules (schedules which are very close to each other in the allocation of tasks) may result in very different outcomes regarding costs and/or constraint violations. For example, while one schedule may not violate any hard constraint and have a relatively low cost compared to other schedules, making one minor change to this one schedule may then result in a new schedule with one or more hard constraint being violated and/or a cost suddenly increasing to an unacceptable value. As a result of this chaotic behavior, conventional approaches for finding optimized solutions for simple problems (e.g. using dichotomy or searching for neighbors of relatively good solutions already identified) are not expected to be successful or helpful as they are expected to be more likely to miss potentially good schedules, for example schedules which may be remote for the schedules considered by the search.
Problems of this kind are classified in the domain of computation complexity theory as NP-complete and NP-hard, meaning that as the problem grows in size, the time taken to deterministically find ideal solutions increases exponentially. Consequently, for any real-life situation with different workers, tasks, hard and soft constraints and aspects to optimize, the computing resources and time required to find the best overall schedule are far too vast to make a search of the best schedule possible or realistic. Thus, heuristic approaches are used to find useable, rather than ideal, feasible solutions within an acceptable amount of time. Such approaches stop when a good enough solution has been identified or when the search has been running for a certain amount of time and the best solution amongst the solutions searched can be identified as the best solution that could be found. These approaches are generally designed to work for a specific problem and can be difficult to adapt for a different problem. In particular, in view of the “no free lunch theorem”, while a first search method may be optimized to address a specific set of problems and be expected to yield good results in a reasonable time with this set of problems, this first method may then be expected to be sub-optimal for another set of problems and a different searching method would have to be devised to optimize the identification of suitable feasible solutions to the other set of problems in a reasonable time. In view of the complexity and the nature of the search, even with the vast computing capabilities now available in computers and computer systems, an exhaustive search is clearly out of reach and while a computer implementation for such a search is considered as being essential for attempting to identify a suitable feasible solution in a reasonable amount of time, it is considered desirable to identify any means by which the computer implementation of such a search can be accelerated and/or simplified.
In other words, due to the difficulties that are faced when trying to improve a search for a suitable schedule, any improvements in the efficiency of the identification of suitable feasible schedules are generally challenging to identify. Also, in view of the complexity of such systems and of the exponential increase for any additional factor added, any such improvements can translate in very significant improvements in the time needed to find a suitable feasible solution and/or in the computing resources required for identifying a suitable solution.